package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * {2,1,3,4,5,6,8,7}
 * 1,3,2,4,5,6,8,7
 */
public class Offer_JZ13 {

    public static int[] reOrderArray (int[] array) {
        List<Integer> listOne = new ArrayList<>();
        List<Integer> listTwo = new ArrayList<>();
        for (int i=0; i<array.length; i++) {
            if(array[i]%2 == 0) listTwo.add(array[i]);
            else listOne.add(array[i]);
        }

        int oneLen = listOne.size();
        int twoLen = listTwo.size();

        for (int i=0; i<oneLen; i++) {
            array[i] = listOne.get(i);
        }

        for (int i=oneLen; i<oneLen+twoLen; i++) {
            array[i] = listTwo.get(i-oneLen);
        }

        return array;
    }

    /**
     * 未跑出来
     * @param array
     * @return
     */
    public static int[] reOrderArray2(int[] array) {
        int index = 0; // 记住交换后从左往右第一个为偶数的下标
        for(int i=0; i<array.length; i++) {
            if (array[i] % 2 == 0) {
                index = i;
                break;
            }
        }

        int i=0;
        while (i < array.length) {
            // 为偶数，且不是数组最后一个数，且下一个数是奇数就进行交换
            if (array[i]%2==0 && i+1<array.length && array[i+1]%2!=0) {
                if (i-index+1 == 1) { // 交换时，奇数和第一个偶数下标如果相差等于1直接交换
                    int temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                    index = i+1;
                } else { // 1,3,2,4,5,6,8,7   index = 2,  i+1=4
                    for (int j=i+1; j>index; j--) {
                        int temp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = temp;
                    }
                }
            }
            i++;
        }

        return array;
    }

    public static void main(String[] args) {
//        System.out.println(Arrays.toString(reOrderArray2(new int[]{2,1,3,4,5,6,8,7})));
        System.out.println(Arrays.toString(reOrderArray2(new int[]{1,2,3,4,5,6,7})));
    }
}
